package sort;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/4/5 22:14
 */
public class 前K个高频元素的quickVersion {










    /*
     先写一下 第 k 个 最大元素 之后， 再 拓展
     AC
     */

    public int recursion(int nums[],int l,int r,int k){
        if(l == r){
            return nums[l];
        }
        int randomIndex = l + (int)(Math.random() * (r - l + 1));
        swap(nums,randomIndex,r);
        int[] partition = partition(nums, l, r);
        if(k >= partition[0] && k <= partition[1]){
            return nums[k];
        }else if(k < partition[0]){
            return recursion(nums,l,partition[0] - 1,k);
        }else{
            return recursion(nums,partition[1] + 1,r,k);
        }
    }


    /*
     改变一下写法：
     > x 的 放 左边
     = x 的放中间
     < x 的放右边
     */
    public int[] partition(int nums[],int l,int r){
        int less = l - 1,more = r ,index = l;
        while(index < more){
            if(nums[index] == nums[r]){
                index++;
            }else if(nums[index] > nums[r]){
                swap(nums,++less,index++);
            }else{
                swap(nums,index,--more);
            }
        }
        swap(nums,more,r);
        return new int[]{less + 1,more};
    }

    public void swap(int nums[],int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }



}
